#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
using T = int;
T rad(); // quick read
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
const int max_size = 5 + 100;
const int maxn = 5 + 100;

ll qpow(ll base, int k) {
    ll ret = 1;
    for (; k; base *= base, k >>= 1) {
        if (k & 1) ret *= base;
    }
    return ret;
}

int n, k;

int main() {
    // rf(i, 10) cout << qpow(2, i) << " ";
    int Q = rad();
    rf(q, Q) {
        n = rad(), k = rad();
        int cnt = 0;
        if (k == 1 || k > 31)
            cnt = n;
        else
            for (int i = 1; 1; ++i) {
                ll l = qpow(i, k);
                if (l > n) break;
                int r = min(qpow(i + 1, k), n + 1LL);
                cnt += (r - 1 - l) / i + 1; // 等差数列通项数量
                // for (int j = l; j < r; ++j) {
                //     if (j % i == 0) cnt++;
                // }
            }
        printf("Case #%d: %d\n", q, cnt);
    }
}

T rad() {
    T back = 0;
    int ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}